1. Field
Example embodiments in general relate to methods of determining influence of a member within an overall dataset in which a plurality of nodes exist, in which the member is represented by one of the nodes in the dataset.
2. Related Art
The following terms, briefly described hereafter, characterize features of the prior art that are relevant to the example embodiments. In computer science, a data structure is an organized collection of data, which may include information about the relationships existing between various members of the collection. In computer science, an Abstract Data Type (ADT) is a set of data together with the operations upon that data. The three fundamental types of ADT are List, Tree and Graph.
A list consists of nodes (containing data) and links between these nodes. A list is thus a “linear” representation of information. Each node in a list has at most one predecessor and at most one successor and may contain two components of information, a “data-component” and a “next-pointer”. A node may be an ordered list of information (data, next-pointer). A list may start with a pointer to the first node on the list. Each subsequent node then may have a pointer to the successor node of that node. The last node of the list should contain a next-pointer value of “NULL” to represent that it is the last node on the list.
Specific types of lists include: Single Linked Lists, Double Linked Lists, Queues, Circular Queues, and Stacks. Operations upon lists include: insert, delete, find and update; special operations for stacks include top, push, pop and flush.
A tree also consists of nodes. Similar to a list, the nodes of a tree can be represented as having two types of components, data and pointers. However, for a tree there may be more than one pointer field. A “binary tree” has two pointer fields called “left child” and “right child”. In general a tree may have any number of children, but trees with two children (binary trees) are widely used.
A tree node can be said to have at most one predecessor (the root node has no predecessor) but may have any number of successor nodes. Also, in the case of trees, predecessor nodes may be referred to as “parent” nodes, and successor nodes as “children”.
FIG. 1 is a block diagram illustrating a conventional tree structure. A term related to trees is the “tree height”. The height of a tree is the largest value derived from counting the parents of all the nodes. In FIG. 1, there is shown a tree structure or tree 10 which has a root node 12 with no predecessor. The root node 12 includes a left sub tree pointer 14 and a right sub tree pointer 15. The left sub tree pointer 14 points to a successor node 24 and the right sub tree pointer 15 points to a successor node 25. Successor node 24 spawns two additional successor nodes 34 and 36, while successor node 25 spawns an additional successor node 36. The height of the tree 10 is 2. The height is also sometimes referred to as the depth.
A graph consists of nodes which have a data component and pointer components. A graph is the most general of the three fundamental data structure types. A graph node may have any number of successor nodes as well as any number of predecessor nodes (a tree node may have at most one predecessor).
FIG. 2 is a block diagram illustrating a conventional graph structure. Within the field of graph theory, there are two fundamentally different types of graphs, “directed” and “undirected”; directed graphs being discussed herein. A directed graph has the sense that two nodes are linked together in an “ordered” fashion, so that a link between two nodes is “from” the predecessor node and “to” the successor node. As shown in FIG. 2 in the graph 20, nodes 42 which have only successors are called “source” nodes. Nodes 44 which have only predecessors are called “sink” nodes. When discussing graphs, references to nodes such as “parent” or “child” are avoided.
A tree may be considered to be a graph which contains no cycles. Hence a tree is a special type of graph. A cycle is a relationship between two or more nodes in which it is possible to return to the starting point without retracing steps. So if one proceeds from node A to node B and then from node B to node C, and further if one proceeds from node C to node A, the member has completed a “cycle”. A cycle is valid in a graph but not valid in a tree.